//
// Created by 123 on 2024/3/17.
//
#include <iostream>

using namespace std;
#define MAX_TREE_SIZE 100



int UFSets[MAX_TREE_SIZE];
//元素下标数组 存数据 下标对应在UFSets中的下标
int Num_Index[MAX_TREE_SIZE];
//最后一个数据所在的下标；
int cur_index=-1;


void initUnLoSet(){
    for (int i = 0; i < MAX_TREE_SIZE; ++i) {
        UFSets[i]=-1;
        Num_Index[i]=-1;
    }
}
//寻找自己的父亲
int findFather(int index);
//合并
void unionNode(int a_num,int b_num);
//是否属于同一集合
bool isSameSet(int a_index,int b_index);


//寻找元素下标
int findIndex(int num);
//加入元素
void add(int num);

void is(int a,int b){
     a= findIndex(a);
     b= findIndex(b);
    if(isSameSet(a,b))
        cout<<"是"<<endl;
    else{
        cout<<"否"<<endl;
    }
}

//int main(){
//
//
//
//
//
//    cout<<(-1)+(-1)<<endl;
//	initUnLoSet();
//    cout<<"=================="<<endl;
//    add(0);
//    add(1);
//    add(2);
//    add(3);
//    add(4);
//    add(5);
//    add(6);
//    add(7);
//    add(8);
//    add(9);
//
//
//    unionNode(6, 0);
//    unionNode(7, 0);
//    unionNode(6, 8);
//
//
//
//    unionNode(4, 1);
//
//    unionNode(4, 9);
//    unionNode(2, 3);
//    unionNode(3, 5);
//
//    for (int i = 0; i < MAX_TREE_SIZE; ++i) {
//        cout<<Num_Index[i]<<"   ----------:  "<<UFSets[i]<<endl;
//
//    }
//
//    is(0,6);
//    is(6,7);
//    is(7,8);
//
//    is(1,4);
//    is(1,9);
//
//    is(2,3);
//    is(5,3);
//
//    is(2,1);
//    is(5,4);
//
//
//
//
//}
void add(int num){
    Num_Index[++cur_index]=num;
}
int findIndex(int num){
    for (int i = 0; i < MAX_TREE_SIZE; ++i) {
        if(num==Num_Index[i])
            return i;
    }
    return -1;
}
//-----------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------
//---------------------------------下面是并查集的操作----------------------------------------
//-----------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------

//寻找自己的父亲
int findFather(int index){
    int root=index;
    while (UFSets[root]>=0){
        root=UFSets[root];
    }
    while (index!=root){
//        x=UFSets[x];
//        UFSets[x]=index;
        int turn=UFSets[index];
        UFSets[index]=root;
        index=turn;
    }
    return root;
//    int x=index;
//    while (UFSets[index]>=0){
//        index=UFSets[index];
//    }
//    while (x!=index){
////        x=UFSets[x];
////        UFSets[x]=index;
//        int turn=UFSets[x];
//        UFSets[x]=index;
//        x=turn;
//    }
//    return index;
}
//合并
void unionNode(int a_num,int b_num){
    int a_index= findIndex(a_num);
    int b_index= findIndex(b_num);
    if(a_index==-1||b_index==-1){
        cout<<"非法数字: "<<a_num<<":   "<<a_index<<"  ----  "<<b_num<<":    "<<b_index<<endl;
        return;
    }
    int a= findFather(a_index);
    int b= findFather(b_index);
    if(a!=b){
        int big=UFSets[a]-UFSets[b]<0?a:b;
        int small=a==big?b:a;
        UFSets[big]=UFSets[small]+UFSets[big];
        UFSets[small]=big;
    }
}
//是否属于同一集合
bool isSameSet(int a_index,int b_index){
    return findFather(a_index)== findFather(b_index);
}
